package com.yequan.leetcode.lrucache.LRUCache_146;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yequan
 * @date 2021/10/12 13:06
 **/
public class Recode2LRUCache {

    private Map<Integer, DBLinkedNode> cache;

    private DBLinkedNode head;
    private DBLinkedNode tail;
    private int capacity;
    private int size;

    Recode2LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        cache = new HashMap<>();
        head = new DBLinkedNode();
        tail = new DBLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    int get(int key) {
        DBLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        move2Head(node);
        return node.value;
    }

    void put(int key, int value) {
        DBLinkedNode node = cache.get(key);
        if (node == null) {
            node = new DBLinkedNode(key, value);
            cache.put(key, node);
            add2Head(node);
            if (++size > capacity) {
                //移除最少使用的,双向链表尾部节点
                DBLinkedNode tailNode = removeTailNode();
                cache.remove(tailNode.key);
                --size;
            }
        } else {
            node.value = value;
            move2Head(node);
        }
    }

    private DBLinkedNode removeTailNode() {
        DBLinkedNode tailNode = tail.pre;
        removeNode(tailNode);
        return tailNode;
    }


    private void move2Head(DBLinkedNode node) {
        removeNode(node);
        add2Head(node);
    }

    private void removeNode(DBLinkedNode node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }

    private void add2Head(DBLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private static class DBLinkedNode {

        DBLinkedNode pre;
        DBLinkedNode next;
        int key;
        int value;

        public DBLinkedNode() {
        }

        public DBLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}
